\documentclass[oneside]{homework} %%Change `twoside' to `oneside' if you are printing only on the one side of each sheet.

\studname{Ran Yu}
\studmail{ry2239@columbia.edu}
\coursename{Analysis of Algorithms}
\hwNo{2}
\uni{ry2239}


\usepackage{graphicx}
\begin{document}
\maketitle

\section*{Problem 1}
\textbf{a.$T(n)=9T(n/3)+n^2$}\\\\
 ~Ans:~$T(n)=\Theta(n^2\log n)$\\
 ~Using the Master Theorem, $a=9,~b=3,~f(n)=n^2$. \\ ~For that $f(n)=n^{\log_ba}=n^2$, $T(n)=\Theta(n^{\log_ba}\log n)=\Theta(n^2\log n)$;\\\\
\textbf{b.$T(n)=2T(n/3)+n$}\\\\
 ~Ans:~$T(n)=\Theta(n)$
 ~Using the Master Theorem, $a=2,~b=3,~f(n)=n$.\\
 ~For that $\log_ba=\log_32<1$, $\exists~\epsilon$ satisfy $f(n)=\Omega(n^{\log_ba+\epsilon})$, and meanwhile, $a\times f(n/b) = 2\times f(n/3)=\frac{2}{3}n$, $\exists~C$ that $C\leq1$ and $a\times f(n/b) \leq C\times f(n)$. According to Master Theorem, $T(n)=\Theta(f(n))=\Theta(n)$\\\\
\textbf{c.$T(n)=3T(n/2)+n$}\\\\
 ~Ans:~$T(n)=\Theta(n^{\log_23})$\\
 ~Using Master Theorem, $a=3,~b=2,~f(n)=n$.\\
 ~For that $\log_ba=\log_23>1$, $\exists~\epsilon$ satisfy $f(n)=O(n^{\log_ba-\epsilon})$, according to Master Theorem, $T(n)=\Theta(n^{\log_ba})=\Theta(n^{\log_23})$.\\\\
\textbf{d.$T(n)=4T(n-2)+1$}\\\\
 ~Ans:~$T(n)=\Theta (2^n)$\\
 ~Expanding the equation,\\
 $T(n)=4T(n-2)+1\\
~~~~~~~=4T(4(n-4)+1)+1\\
~~~~~~~=16T(n-4)+1+4\\
~~~~~~~\dots\\
~~~~~~~=4^kT(n-2k)+\sum_{i=0}^{k-1}4^i\\
~~~~~~~=4^{\lfloor \frac{n}{2}\rfloor}T(0~or~1)+\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor-1}4^i\\
~~~~~~~=4^{\lfloor \frac{n}{2}\rfloor}C+\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor-1}4^i\\
~~~~~~~=\Theta(2^n)\\$\\
\textbf{e.$T(n)=T(\sqrt{n})+1$}\\\\
 ~Ans:~$T(n)=\Theta(\log\log n)$\\
 ~Set $m=\log n$; The equation could be rewrite as:\\
$T(2^m) = T(2^{\frac{m}{2}})+1\\
~~~~~~~=T(2^{\frac{m}{4}})+1+1\\
~~~~~~~\dots\\
~~~~~~~=T(2^{\frac{m}{2^k}})+k\\
~~~~~~~=T(C)+k\\
~~~~~~~=T(C)+\log m\\
~~~~~~~=\Theta(\log m) = \Theta(\log \log n)\\$\\
\textbf{f.$T(n)=T(n/2)+T(n/4)+n$}\\\\
Ans:~$T(n)=\Theta(n)$\\
Let us try the Recursive Tree method.
\begin{figure}[!ht] 
     \centering   
     \includegraphics[width=14cm, height=6cm]{rt.pdf} 
     \caption{Recursive tree of question f} 
\end{figure}

We can get from figure 1, that the tree here is not balanced: the longest path is the leftmost one, and its length is $\log n$.\\
$T(n)\leq 2^{\log n}\times T(C)+n\times(1+\sum_{i=1}^{\log n}{(\frac{3}{4})}^i)\\
~~~~~~~\leq C_1(n)$\\
And the shortest path is the rightmost one, and its length is $\log_4 n$.\\
$T(n)\geq 4^{\log_4 n}\times T(C)+n\times(1+\sum_{i=1}^{\log_4n}{(\frac{3}{4})}^i)\\
~~~~~~~\geq C_2(n)$\\
Therefore, we get $T(n)=\Theta(n)$
\section*{Problem 2}
a.Assume there are $i$ Good Chips and $j$ Bad Chips.\\\\
 If $i>j$ then for any good chip, test it with all the rest of the chips, the test result must be 'More than half of the chips say it is good'. For, the amount of bad chips is less than half, so even they conspire to fool the professor-say the good one is bad, they cannot fake the result as 'More than half of the chips say it is bad'. And once we know one single chip is a Good Chip, we can get all the correct result of other chips for that Good chip always tell the truth.\\
 But if $i<j$, Bad Chips can conspire to confuse us and we cannot make any credible conclusion. Assume all $i$ Good Chips consist a set named $A$, and because of $i<j$, Bad chips can pick out $i$ Bad Chips consist a set named $B$ as $Fake Good Chips$, and the rest of $j-i$ Chips as set called $C$ of Bad Chips. No matter what strategy we choose, we cannot distinguish $Set ~A$ from $Set~ B$ for all the Bad Chips in $Set ~B$ show the exactly Good Chip Performance.  In this way, no conclusion and result is reliable.\\\\
 b.Let's define an operation on reducing the size of the problem, call it F(A).\\\\
 (1) if n is even, then there are at least 2 more Good Chips than Bad Chips.\\
 Split chips into 2 Arrays, A and B. \\
 For every pair, test A[i] and B[i].\\
$~~$ if (A[i]:B[i] = Good:Good) delete A[i] or B[i] randomly;\\
$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$ else delete A[i] and B[i];\\
We can see that after every recursion, we delete at least half of the chips, and reduce the problem into half of before. \\
And in the array left we can show that Good Chips are still more than Bad ones: \\Let us assume there are $a$ pairs of Good:Good Chips pair, $b$ pairs of Bad:Bad, and $c$ pairs of Bad:Good, and 'The amount of  Good Chips$(2\times a +c)$ is larger than The Amount of Bad Chips$(2\times b+c)\Rightarrow(a>b)$'; so after the reduction, we get $a$ Good chips and $b$ Bad chips left, and as what proved before, a$>$b, so there is still more Good Chips left. Therefore, after recursions, the only chip left is good chip.\\
In this way, the $\lfloor \frac{n}{2}\rfloor$ pairwise tests are done and the problem size is reduced to half.\\
(2) if n is odd. There are at least 1 more Good Chips than Bad Chips.\\
Randomly pick out one chip, and split the rest of chips into 2 arrays, and run the operation before. \\
From the analysis of the operation in (1), we can get that the chips we delete at every recurrence, at least contain half of Bad Chips. And every time after recurrence, the chips left have at least half of Good Chips. Therefore, if odd number of chips left after several recurrence, there must be at least one more Good Chip than Bad ones.  And we put the picked out one into the array and the problem change back the EVEN-Number problem above. Continue do the recursion, the remaining chip is good chip; \\
If the number of the remaining chips is always even, then the chip left after recursions is a good one; if no chips left after recursions,  then the picked-out one is a good one. \\
The condition of odd number chips is a little complicated than even one, but it also use the operation above, which reduce half of the problem after every recursion. And every recursion need $\lfloor \frac{n}{2}\rfloor$ pairwise tests.\\
c.From the analysis above, we get that if the number of good chips is more than half of the sum, every recursion reduce half of the problem. So the running time equation could be written as $T(n)=T(n/2)+n/2$, and it is easy to get $T(n)=\Theta(n)$; And the recurrence showed as answer b.\\
\section*{Problem 3}
1. $P=\frac{1}{n-i+1}$\\\\
2. $E=\sum_{i=0}^{n-1}\frac{1}{n-i}=\frac{1}{2}\times(\frac{1}{n}+\frac{1}{n-1}+\dots+1)\\
~~~~~~~~~~~~~~~~~~~~~~~=\frac{1}{2}\times(\ln(n)+C)=\Theta(\log n)$\\
\section*{Problem 4}
1. For in the original partition function, it has not take the equal elements condition under consideration. So if the array is consisted of equal elements at all, every recurrence produces one sub-problem with $n-1$ elements and one with $0$ elements. Therefore, we get Running Time as $T(n)=T(n-1)+T(0)+\Theta(n)=\Theta(n^2)$.\\\\
2.The Modified-Partition is written below,\\
Modified-PARTITION($A, ~p,~ r$)\\
$1~~~ x=A[r];\\
2~~~i=p-1;\\
3~~~n=r;\\
4~~~j=p;\\
5~~~$\textbf{while}$~j\leq~n-1\\
6~~~~~$\textbf{if}$A[j]<x\\
7~~~~~~~i=i+1;\\
8~~~~~~~$exchange$~A[i]$ with $A[j]\\
9~~~~~~~j=j+1;\\
10~~~~$\textbf{elseif}$~A[j]=x\\
11~~~~~~~n=n-1;\\
12~~~~~~$exchange$~A[j]$ with $A[n]\\
13~~~~$\textbf{else}$~j=j+1;\\
14~~$\textbf{for}$~k=i+1~$\textbf{to}$~r-n+i+1\\
15~~~~~~$exchange$~A[k]~$with$~A[k+n-i]\\
16~~$\textbf{return}$~i+1,r-n+i+1$\\\\
3.Modified Randomized quicksort is written below,\\
Modified-RANDOMIZED-QUICKSORT($A,~p,~r)\\
1~~~$\textbf{if}$~p<r\\
2~~~~~q_1,q_2=$Modified-RANDOMIZED-PARTITION($A,~p,~r)\\
3~~~~~$Modified-RANDOMIZED-PARTITION($A,~p,~q_1-1)\\
4~~~~~$Modified-RANDOMIZED-PARTITION($A,~q_2+1,~r)\\$
Modified-RANDOMIZED-PARTITION($A,~p,~r)\\
1~~~i=$RANDOM$(p,~r)\\
2~~~$exchange$~A[r]~$with$~A[i]\\
3~~~$\textbf{return}Modified-PARTITION($A,~p,~r$)\\
Every recurrence in Modified-RANDOMIZED-QUICKSORT the call of Modified-RAN-DOMIZED-PARTITION divide the input array into 3 part, where $A[p,\dots, q_1-1]<pivot$, $A[q_1,\dots,q_2]=pivot$, and $A[q_2+1,\dots,r]>pivot$, and we only sort the $A[p,\dots, q_1-1]$ and $A[q_2+1,\dots,r]$ part then. This effectively prevent the case of equal elements that slow down the sort. Therefore, the running time will not be the worst case.\\
For the handling of equal elements do not increase the running time of the Modified-PARTITION function, in Modified-RANDOMIZED-QUICKSORT, we could simply treat the equal elements as a group of elements that performs as pivot together. In this way, the running time of Modified-RANDOMIZED-QUICKSORT have the same running time with RANDOMIZED-QUICKSORT, it is $O(n\log n)$\\
\section*{Problem 5}
I use the SELECT Algorithm introduced in the CLRS. SELECT( $A,~i)$ means select the $i$th smallest of the input array A.\\
Group-SELECT($S,~k)\\
1~~~A_m=$SELECT$(S,\lfloor length(A)/2 \rfloor);\\
2~~~$\textbf{for}$~i=1~$\textbf{to}$~length(A)\\
3~~~~~M[i]=|A[i]-A_m|;\\
4~~~M_k=$SELECT$(M,~k);\\
5~~~$\textbf{for}$~i=1~$\textbf{to}$~length(A)\\
6~~~~~$\textbf{if}$~|A[i]-A_m|\leq M_k\\
7~~~~~~~Set.add(A[i]);\\
8~~~$\textbf{return}$~Set;\\$
The running time of SELECT Algorithm is $O(n)$, and other for-loops are iteration of the array, hence all the algorithm is an $O(n)$-time algorithm.
\section*{Problem 6}
Because the problem is about how to minimize the total length of south-north spurs, we can only consider about the main pipeline's y-coordinate. The optimal y-coordinate of the main pipeline is the median of the y-coordinates array of the wells. If the number of the array is even, then any position that between the median 2 y-coordinates of the array is ok.\\
And I simply justify this conclusion. See Figure 2,
\begin{figure}[!ht] 
     \centering   
     \includegraphics[width=14cm, height=6cm]{P6.pdf} 
     \caption{Main Pipeline Problem} 
\end{figure}
If the main pipeline located at the solid-black line I draw, then the distance of these 2 well to main pipeline would be $l3+l4$, and if the main pipeline located at the line in the middle, the distance would be $l1+l2$. We can easily see from the Figure, that $l3+l4=l1+l2+2\times l4 \Rightarrow l3+l4>l1+l2$. Because for any 2 well-pair, their minimum spurs length would be the y-coordinates differences. In order to get the minimum spurs length for all the wells, the main pipeline has to located in the middle of all the wells, the position I mentioned before. Any other positions would cause the problem like this: not the minimum length of the pipeline.
The algorithm would simply be the SELECT Algorithm in the CLRS.
\end{document}